|
In graph theory, coloring generally implies assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where in each incidence of an edge with a vertex is assigned a color under certain constraints. ==Definitions== Let ''G = (V, E)'' be a simple graph with vertex set (non-empty) ''V(G)'' and edge set ''E(G)''. An incidence is defined as a pair ''(v, e)'' where ''v'' ϵ ''V(G)'' is an end point of ''e'' ϵ ''E(G)''. In simple words, one says that vertex ''v'' is incident to edge ''e''. Consider a set of incidences, say, ''I(G)'' = .〔Brualdi R. A.; Massey J. Q.(1993), "(Incidence and strong edge colorings of graphs )", Discrete Mathematics 122, pp. 51–58〕 The two incidences ''(v,e)'' and ''(u,f)'' are said to be adjacent if one of the given conditions holds: * ''v'' = ''u'', ''e'' ≠ ''f'' * ''e'' = ''f'', ''v'' ≠ ''u'' * ''e'' = ', ''f'' = ' and ''v'' ≠ ''w''. An incidence coloring of ''G'' can be defined as a function ''c'': ''I(G)'' → ''N'' such that ''c((v, e))'' ≠ ''c((u,f))'' for any incidences ''(v, e)'' and ''(u, f)'' that are adjacent. This implies that incidence coloring assigns distinct colors to neighborly incidences. (a simplified notation ''c(v, u)'' is used instead of ''c((v, e))''. ) The minimum number of colors needed for incidence coloring of a graph is known as incidence chromatic number or incidence coloring number of ''G'', represented by ''(G)''. This notation was introduced by Jennifer J. Quinn Massey and Richard A. Brualdi in 1993. Let ''A'' be a finite subset of ''N'', the set of natural numbers. ''A'' is an interval if and only if it contains all the numbers between minimum of ''A'' and maximum of ''A''. Consider ''c'' to be an incidence coloring of graph ''G''. Let ''(v)'' = . An interval incidence coloring of ''G'' is an incidence coloring ''c'' of graph ''G'' such that for each vertex ''v'' in ''V(G)'', the set ''(v)'' is an interval.〔Janczewski, R.; Malafiejska, A.; Malafiejski, M., "Interval Wavelength Assignment in All-optical Star Networks", Parallel Processing and Applied Mathematics, 8th International Conference, PPAM 2009, Wtroclaw, Poland, September 13–16, 2009. Revised Selected Papers Part I (Springer), pp. 11–20, doi:10.1007/978-3-642-14390-8_2, ISBN 978-3-642-14389-2〕 The interval incidence coloring number of ''G'' is the minimum number of colors used for the interval incidence coloring of ''G''. It is denoted by ''IIC(G)''. If only ''IIC(G)'' colors are used for the interval incidence coloring, then it is said to be minimal. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Incidence coloring」の詳細全文を読む スポンサード リンク
|